'''
    最短路径算法：Dijkstra算法，用来计算图中一个点到另一个点的最短路径，地图中应该经常使用。
    这个算法原来在计算机网络中学过，其实主要是用来路由的，此算法有一个要求是需要知道所有线上的权重。
    算法流程：
        1. 选定一个初始节点，该节点距离设置为0
        2. 寻找邻居节点，并计算该节点到邻居节点的位置，判断该位置是否小于邻居节点存储的位置，是则替换邻居节点存储的距离，使其存储最小距离。
        3. 将上述节点和位置存储入最小队列，设置前驱
        4. 取最小队列中的最小值，重复上述行为。
'''

# 书中采用二叉树队列，但其实可以不用，可以直接通过排序删除的方式进行，该方法复杂度会比较高
from graph import Graph, Vertex

# 实现一个二叉堆的构造函数，小根堆
class PriorityQueue:
    def __init__(self):
        self.heaplist = [(0,0)]
        self.currentSize = 1

    # 插入元素,这里面当Vert相同时要覆盖
    def decreaseKey(self,nextVert,newDist):
        i = self.currentSize    # list长度
        repeat = False

        while i > 0:
            if nextVert == self.heaplist[i-1][1]:
                repeat = True
                self.heaplist[i-1] = (newDist,nextVert)
                self.percDown(i-1)
                self.percUp(i-1)
            i = i - 1
        if not repeat:
            self.heaplist.append((newDist,nextVert))
            self.currentSize = self.currentSize + 1
            self.percUp(self.currentSize)   # 维护堆顺序

    def __contains__(self, item):
        return item in [y[1] for y in self.heaplist]

    # 删除元素,一般都是删除顶部元素
    def delMin(self):
        retval = self.heaplist[1]   # 根元素
        self.heaplist[1] = self.heaplist[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heaplist.pop() # 删除最后一个元素
        self.percDown(1)    # 维持堆顺序
        return retval[1]

    # 输入一个列表，将列表转化成堆结构和堆顺序，只需要从最后叶子结点的父节点开始检查直到检查到根节点。
    def buildHeap(self,alist):
        i = len(alist)//2   # 第一个父节点
        self.currentSize = len(alist)
        self.heaplist = [(0,0)] + alist[:]
        while i > 0:
            self.percDown(i)
            i = i - 1

    # 删除元素后的堆顺序维持，就是根节点通过排序移到合适位置。
    # 思路：跟节点和左右节点比较(前提是有节点，即i*2<size)。左右节点先比较，我们取那个小一点的节点，然后根节点和这个节点交换位置
    # 输入某一个节点位置，从该节点向下实现排序满足该位置的堆顺序结构
    def percDown(self,i):
        while (i * 2) <= self.currentSize:  # 说明有子节点
            mc = self.minChild(i)   # 最小的子节点
            if self.heaplist[i][0] > self.heaplist[mc][0]:
                temp = self.heaplist[i]
                self.heaplist[i] = self.heaplist[mc]
                self.heaplist[mc] = temp
            i = mc

    def minChild(self,i):
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heaplist[i * 2][0] < self.heaplist[i * 2 + 1][0]:
                return i * 2
            else:
                return i * 2 + 1

    # 插入元素后维持堆顺序
    def percUp(self,i):
        while i//2 > 0: # 直到根节点
            if self.heaplist[i][0] < self.heaplist[i//2][0]:
                tmp = self.heaplist[i//2]
                self.heaplist[i//2] = self.heaplist[i]
                self.heaplist[i] = tmp
            i = i//2

    def isEmpty(self):
        if self.currentSize > 1:
            return False
        else:
            return True

def dijkstra(aGraph,start):
    pq = PriorityQueue()
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(),v) for v in aGraph])
    # print(pq.heaplist)
    while not pq.isEmpty():
        currentVert = pq.delMin()
        # print(currentVert.getId())
        for nextVert in currentVert.getConnections():
            newDist = currentVert.getDistance() \
                    + currentVert.getWeight(nextVert)
            if newDist < nextVert.getDistance():
                nextVert.setDistance( newDist )
                nextVert.setPred(currentVert)
                pq.decreaseKey(nextVert,newDist)


# def dijkstra(aGraph,start): # 输入图与开始节点
#     start.setPred(None)
#     start.setDistance(0)
#     pq = [] # 用来存储顶点及对应的距离，原文使用堆来进行存储
#     for v in aGraph:
#         pq.append((v.getDistance(),v))
#
#     while len(pq) > 0:
#         currentVert = delMin(pq)
#         for nextVert in currentVert.getConnections():
#             newDist = currentVert.getDistance() \
#                     + currentVert.getWeight(nextVert)
#             if newDist < nextVert.getDistance():
#                 nextVert.setDistance(newDist)
#                 nextVert.setPred(currentVert)
#                 decreaseKey(pq,nextVert,newDist)

def decreaseKey(pq,nextVert,newDist):
    pq.append((newDist,nextVert))
    pq.sort(reverse=True, key=lambda x: x[0])  # 按照距离降序排列

# 得到pq中的最小值
def delMin(pq):
    pq.sort(reverse= True,key=lambda x:x[0])    # 按照距离降序排列
    # print(pq)
    return pq.pop()[1]




if __name__ == '__main__':

    graph_dict = {
        "A": {"B": 5, "C": 1},
        "B": {"A": 5, "C": 2, "D": 1},
        "C": {"A": 1, "B": 2, "D": 4, "E": 8},
        "D": {"B": 1, "C": 4, "E": 3, "F": 6},
        "E": {"C": 8, "D": 3},
        "F": {"D": 6},
    }
    g = Graph()  # 创建图
    # 创建图
    for v in graph_dict:
        for w in graph_dict[v]:
            g.addEdge(v,w,graph_dict[v][w])

    # 打印图：
    print('图创建如下:')
    for v in g: # 这个返回的是键值：顶点
        for w in v.getConnections():
            print('\t(%s,%s,%s)' %(v.getId(),w.getId(),v.connectTo[w]))

    dijkstra(g,g.getVertex('A'))

    #打印出最短路径,需要反序打印，当然可以用栈
    print('各顶点最短路径：')
    for v in g: # 遍历g中的顶点。
        h = v
        res = []
        res.append([h.getId()])
        print(h.getId(),':')

        while h.getPred() != None:
            h = h.getPred()
            # print(h.getId())
            res.append(h.getId())

        i = len(res)
        while i > 1:
            print(res[i-1],'->',end='')
            i = i - 1

        print(res[0][0],end='')
        print(': ',v.getDistance())

